1. Field of the Invention
This invention relates generally to broadband switching and, more particularly, to the design of the sub-microsecond switching and control over a massive broadband switching network.
2. Description of the Background Art
As telecommunication systems have evolved, the demand for bandwidth has been ever increasing in both transmission and switching. Advances in fiber optics afford ample transmission capacity, while switchingxe2x80x94the technology that puts transmission capacity to flexible usexe2x80x94has not kept pace. Because the scale of a switching fabric is subject to various constraints (e.g., electronic or physical), a large switch is often constructed from the networking of smaller ones. Thus, for example, the public switched telephone network is an interconnection of numerous switch offices; likewise, the core of the modern digital switching system is typically a multi-stage network of smaller switches. Most important, in this modern era of broadband communications, countless primitive switching units inside a single chip are integrated into a large switch. Massive integration of switching components has been a fertile area of research and exploratory development efforts.
The results of such efforts are generally ad hoc in nature, without rigorous underpinnings; such underpinnings, when uncovered, lead to general elucidating principles and, accordingly, more efficient implementations of switching networks follow naturally from the principles. In this way, known but specific industrial designs and/or commercial applications are understood as merely special cases of a broad array of cases. From another viewpoint, sporadic findings in the literature translate into instances of different special cases of the general principles.
By way of a heuristic example of the benefit of uncovering foundational principles, a switching network at a microscopic level is first considered to illustrate the foregoing observations. It is known in the art that efficacious control over a packet switching network composed of nodes is effected whenever the switching decision at each node is determined only by information carried in each local input data packet to the node; such a control mechanism is called xe2x80x9cself-routingxe2x80x9d. The concept of xe2x80x9cself-routingxe2x80x9d was initially disclosed by D. H. Lawrie in an article entitled xe2x80x9cAccess and alignment of data in an array processor,xe2x80x9d as published in IEEE Trans. Comp., vol. 24, pp. 1145-1155, 1975. Lawrie postulated the following in-band control mechanism for a specific banyan-type network (called the Omega network) composed of a cascade of stages wherein each stage is further composed of a number of two-input/two-output switching cells: upon entering the network, a data packet composed of a sequence of bits is prepended with its binary destination address in the form d1d2 . . . dn. The bit dj indicates the preference between the only two outputs of a stage-j switching cell and is consumed by the stage-j switching control. Thus, the switching state of a cell is determined by just this leading bit of each of the two input packets. The existing self-route mechanism used in this particular banyan-type network considered by Lawrie is ad hoc, that is, determination of the routing tag of a packet is one of trial-and-error. The main reason behind the trial-and-error procedure is that Lawrie has not had the benefit of a fundamental theoretical approach to determine the routing tag for self-routing, as covered in the sequel by the inventive subject matter in accordance with the present invention. The theoretical underpinnings are founded upon the concept of xe2x80x9cguide of a bit-permuting networkxe2x80x9d, which is a sequence of numbers, whereby the guide ensures that the routing tag for any given bit-permuting network can be determined once the guide of that network is computed. As will be shown, the guide of the networks studied by Lawrie happens to be a special case wherein the guide is the monotonically increasing 1, 2, . . . , n. The destination address can no longer be used as the routing tag for any other banyan-type network whose guide is not monotonically increasing. For this reason, those banyan-type networks whose routing tag xe2x80x9cseems not relatedxe2x80x9d to the destination address have not been widely studied. But, ironically, those widely studied networks, including the Omega network studied by Lawrie, are actually the most anti-optimal ones with regard to the layout complexity under the popular xe2x80x9c2-layer Manhattan model with reserved layersxe2x80x9d among a huge family of equivalent networks.
The issues of equivalence among networks and optimization of layout complexity brings up a second example highlighting the shortcomings of the past methods. If all those widely studied networks are not optimal, then what networks are optimal and can used to replace the widely studied ones or how to construct such optimal networks in a systematic way need to be explored. The present invention addresses these problems.
All banyan-type networks are equivalent in a weak sense, but in some applications only equivalent networks in a stronger sense can be deployed in replacement of each. A related example of the shortcomings of the existing art is the lack of a systematic way for the adaptation of one network into an equivalent of another in strong senses.
A fourth motivating example, which considers a switching network at a macroscopic level, relates to the properties of a switching network itself. The component complexity of an Nxc3x97N nonblocking network is at least N2/4 (Here the definition of a nonblocking network requires the network to be unique-routing to begin with, because otherwise there are different senses for a network to be xe2x80x9cnonblockingxe2x80x9d.) The quadratic order in this bound indicates the intrinsically high complexity in the nonblocking property of the network. So instead of applying a nonblocking network in switch design, the focus is on uncovering simple networks that preserves xe2x80x9cconditionally nonblocking propertiesxe2x80x9d of switches and thereby construct large conditionally nonblocking switches out of small ones in an economical way. Recursive applications of such construction then leads to conditionally nonblocking switches of indefinitely large sizes. Such theoretical recursive property then allows the physical construction of switching fabric at a throughput level much higher than that of existing routers/switches by the contemporary ASIC technology. In the literature, there are individual instances of certain conditionally nonblocking switches constructed by switching networks, such as the one disclosed by A. Huang and S. Knauer in an article entitled xe2x80x9cStarlite: a wideband digital switch,xe2x80x9d as published in Proceedings of Globecom ""84, Atlanta, pp. 121-125, 1984. However, these instances of conditionally nonblocking property are not preserved by simple network and hence do not enjoy the advantage of recursive construction.
Banyan-type networks as recursive applications of 2-stage interconnection or, at least, equivalent to such recursive applications. In contrast with 3-stage alternate-routing switching that is popular in telephony, 2-stage switching network is more compact in nature and thereby facilitates the VLSI implementation of massive recursive application. More importantly, the unique-routing nature of 2-stage switching is more compatible with sub-microsecond control inside a broadband switching chip. A fifth example of deficiency of the existing art is in the systematic method of physical implementation of recursive 2-stage interconnection that takes advantage of today""s technologies in making switching fabrics at a much higher level of throughput than all largest existent routers.
The critical problem with 2-stage switching is blocking, and one way to alleviate the blocking problem is by xe2x80x9cstatistical line groupingxe2x80x9d, which replaces every interconnection line in the network by a bundle of lines and, at the same time, dilates the size of every node proportionally. A critical issue in applying the method of statistical line grouping lies in the choice of the switch to fill the role of a dilated node. The selected switch does not have to be a nonblocking switch but needs some partial nonblocking property that is articulated in the present invention (Partial nonblocking property is more economically achievable than the full nonblocking property of a switch.) Meanwhile, the control over the selected switch must also be compatible with sub-microsecond control inside a broadband switching chip. Ideally, there should be a self-routing mechanism inside the selected switch that can be smoothly blended with the self-routing mechanism over the banyan-type network. A final example highlighting the shortcomings of the past methods is the lack of a clearly superior candidate for this selected switch. The present invention proposes xe2x80x9cconcentratorxe2x80x9d as a perfect candidate. When multicast switching is involved, then a xe2x80x9cmulticast concentratorxe2x80x9d replaces the concentrator.
The shortcomings of the prior art, as well as other limitations and deficiencies, are obviated in accordance with the present invention by applying algebraic principles to the physical realization of a large switching fabric based upon contemporary technologies.
In accordance with a broad method aspect of the present invention, a method for implementing a class of Nxc3x97N unimodal-circular nonblocking switches each serving a connection request to route a plurality of incoming signals and for enabling the service of any connection request in a nonblocking way on the condition that the connection request is compliant to certain constraints, the method for each of the unimodal-circular nonblocking switches includes: (a) configuring a switch defined by a set of connection states and having an array of N input ports with N distinct input addresses 0, 1, . . . , Nxe2x88x921 and an array of N output ports with N distinct output addresses 0, 1, . . . , Nxe2x88x921, the switch accommodating every complete matching between all N input addresses and all N output addresses by one of its connection states on the condition that, under the matching, the input addresses are a circular unimodal function of the output addresses, where a complete matching between all N input addresses and all N output addresses is equivalent to a combination of N concurrent point-to-point connections from the N input addresses to the N output addresses, and wherein said constraints on the connection request are that: there exists a combination of N concurrent point-to-point connections corresponding to a complete matching accommodated by the switch such that each of the incoming signals in the connection request arriving at a distinct one of the input ports and destined for a distinct one of the output ports determines a point-to-point connection which coincides with one of the point-to-point connections of said combination of N concurrent point-to-point connections accommodated by the switch; and (b) routing the incoming signals from their respective input ports to the corresponding output ports by activating one of the connection states such that the activated one of the connection states accommodates the connection request subject to said constraints on the connection request.
In accordance with a broad system aspect of the present invention, a class of Nxc3x97N unimodal-circular nonblocking switches each serving a connection request to route a plurality of incoming signals and for enabling the service of any connection request in a nonblocking way on the condition that the connection request is compliant to certain constraints, each of the unimodal-circular nonblocking switches includes: (a) a switch defined by a set of connection states and having an array of N input ports with N distinct input addresses 0, 1, . . . , Nxe2x88x921 and an array of N output ports with N distinct output addresses 0, 1, . . . , Nxe2x88x921, the switch accommodating every complete matching between all N input addresses and all N output addresses by one of its connection states on the condition that, under the matching, the input addresses are a circular unimodal function of the output addresses, where a complete matching between all N input addresses and all N output addresses is equivalent to a combination of N concurrent point-to-point connections from the N input addresses to the N output addresses, and wherein said constraints on the connection request are that: there exists a combination of N concurrent point-to-point connections corresponding to a complete matching accommodated by the switch such that each of the incoming signals in the connection request arriving at a distinct one of the input ports and destined for a distinct one of the output ports determines a point-to-point connection which coincides with one of the point-to-point connections of said combination of N concurrent point-to-point connections accommodated by the switch; and (b) control circuitry, coupled to the switch, for routing the incoming signals from their respective input ports to the corresponding output ports by activating one of the connection states such that the activated one of the connection states accommodates the connection request subject to said constraints on the connection request.